/*
用链式存储结构实现队列（非环形）
*/

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

struct DataNode
{
    char data;
    struct DataNode * next;
};

//定义了头结点的链表类，队列需要维护两个头结点
struct LinkQuNode
{
    DataNode * front;
    DataNode * rear;
};

void InitQueue(LinkQuNode * q);

void DestoryQueue(LinkQuNode * q);

bool QueueEmpty(LinkQuNode *q);

bool enQueue (LinkQuNode * q, char e);

bool deQueue(LinkQuNode * q);

// void Output(LinkQuNode * q)
// {
//     if(q -> front != NULL) 
//     {
//         cout<< q->front->data<<" ";
//         q-> front = q -> front ->next;

//     }
// }

void Output(LinkQuNode* q) {
    DataNode* p = q->front; // 使用临时指针遍历队列  
    while (p != NULL) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

int main()
{
    LinkQuNode * q = (LinkQuNode * ) malloc(sizeof(LinkQuNode));
    InitQueue(q);
    enQueue(q,'A');
    // enQueue(q,'B');
    // enQueue(q,'C');
    Output(q);
   //DestoryQueue(q);
    deQueue(q);
    cout<<"队头删除一个元素"<<endl;
    deQueue(q);
    deQueue(q);
   
    Output(q);
    return 0;
}

void InitQueue(LinkQuNode * q)
{
    //如果这里声明为局部变量，函数一结束  该内存不就释放了吗
    q->front = q->rear = NULL;

}


void DestoryQueue(LinkQuNode * q)
{
    DataNode * pre = q ->front,*p;
    if(pre != NULL)
    {
        p = pre -> next;
        while(p != NULL)
        {
            free(pre);
            pre = p;
            p = p ->next;
        }
        free(pre);
    }
    free(q); // 连q节点也删除了，故无法执行后续的操作
    // q节点是队列
}

bool QueueEmpty(LinkQuNode *q)
{
    // if( q ->front == q ->rear ) return true; 该判断表示头结点和尾结点指向同一个位置
    if (q-> front == NULL) 
    {
        return true;
    }

    return false;
}

bool enQueue (LinkQuNode * q, char e)
{

  
    DataNode * dNode = (DataNode * )malloc(sizeof(DataNode));
    dNode ->data = e;
    dNode ->next = NULL;

    if(q -> front == NULL)//若链队为空，则当前节点既是首节点也是尾结点
    {
        q ->front = q -> rear = dNode;
        return true;    //第一次插入之后没有正确的返回，而是继续执行了后续的代码
    }
    // 采用尾插法插入节点
    // q -> rear 找到当前尾结点 q ->rear->next 找到下一个指针域
    q ->rear->next = dNode;
    q ->rear = dNode;
    return true;
}
// 队列只允许头删除，故不实现按元素值删除的逻辑
bool deQueue(LinkQuNode * q)
{
    // 在函数内部开一个临时变量，展示保存将要被删除的节点
    DataNode * dNode = q -> front;

    // 首先判断该操作是否能够正常执行
    if(QueueEmpty(q))
    {
        cout<<"队列中已经没有元素"<<endl;
        return false;
    }

    q -> front  = q ->front ->next;
    if(q ->front == NULL)
    {
        q->rear = NULL; // 队列为空时，rear也应指向NULL
    }
    free(dNode);
    return true;
}

